//
// Created by Lenovo on 2021/12/26.
//

#ifndef BITREE_LINK_BITREE_H
#define BITREE_LINK_BITREE_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

enum Status{OK=1,ERROR=-2,TRUE=1,FALSE=0,EMPTY=-1,OVERFLOW_=-1};
typedef enum Status Status;

typedef char TElemType;

typedef struct BiTNode { //二叉树结点类型
    TElemType data;
    struct BiTNode  *lchild, *rchild;	//左右孩子指针

}BiTNode, *BiTree;

///////////////////////////////////////////////BITREE///////////////////////////////////////////////////////////////////

Status InitBiTree(BiTree T);    //初始化树，构造空二叉树
Status DestroyBiTree(BiTree *T); //销毁二叉树，初始条件：二叉树已存在

//CreateBiTree(BiTree T,definition);    //definition为构造二叉树的定义，按照定义构造二叉树
int CreateBiTree(BiTree *T);//先序创建二叉树,用'.'表示空结点

Status ClearBiTree(BiTree *T);   //将二叉树清为空树，初始条件：二叉树已存在
Status BiTreeEmpty(BiTNode T);  //若二叉树为空返回TRUE，否则返回FALSE
Status BiTreeDepth(const BiTree T);  //获取二叉树的深度，初始条件：二叉树已存在
BiTree Root(BiTNode T); //获取二叉树的根节点，初始条件：二叉树已存在
TElemType Value(BiTNode T,BiTNode* e);    //返回e中的结点数据，初始条件：二叉树T已存在，e为二叉树中的结点
Status  Assign(BiTree T,BiTNode* e,TElemType value);  //将结点e的值赋值为value，初始条件：二叉树T存在，e为二叉树中的结点
BiTNode* Parent(BiTree T , BiTNode* e); //若e是二叉树的非根结点，返回它的双亲，否则返回NULL
BiTNode* LeftChild(BiTree T,BiTNode* e); //返回e的左孩子，没有左孩子返回空，初始条件：二叉树存在，e是二叉树的结点
BiTNode* RightChild(BiTree T,BiTNode* e);    //返回e的右孩子，没有右孩子返回空，初始条件：二叉树存在，e是二叉树的结点
BiTNode* LeftSibling(BiTree T,BiTNode* e);   //返回e的左兄弟，若e为T的左孩子或无左兄弟，返回空，初始条件：二叉树T存在，e是二叉树中的结点
BiTNode* RightSibling(BiTree T,BiTNode* e); //返回e的右兄弟，若e为T的右孩子或无右兄弟，返回空，初始条件：二叉树存在，e是二叉树中的结点
Status InsertChild(BiTree T,BiTNode* p,int LR,BiTNode* C);  //根据LR为0或1，插入C为T中p所指结点的左或右子树，p所指系欸但的原有左或右子树则成为C的右子树
//初始条件，二叉树T存在，p指向T中某一个结点，LR为0或1，非空二叉树不与T相交并且右子树为空
BiTNode DeleteChild(BiTree T,BiTNode* p,int LR);    //根据LR为0或1，删除T中p所指结点的左或右子树
void PreOrderTraverse(BiTree T, int (* Visit)(char e));//先序遍历
void InOrderTraverse(BiTree T,int (*visit)(TElemType e));//中序遍历
void PostOrderTraverse(BiTree T,int (*visit)(TElemType e));//后序遍历
void LevelOrderTraverse(BiTree  T,int (*visit)(TElemType e));//层次遍历

int NumOfLeaves(BiTree T);  //获取树的字节结点个数
Status Whether_E_InBiTree(BiTree T,BiTNode* e);//结点e是否在T中；

////////////////////////////////////////////////////////TREE STACK//////////////////////////////////////////////////////

typedef struct Ele{
    BiTree data;
    struct Ele* pre;
}Ele;

typedef struct Stack{
    Ele* top;
    Ele * base;
    int Stacksize;
}Stack;

Status StackInit(Stack* st);//List Stack Initiate
Status PushBiTree(Stack* sta,BiTree data);//Element In Stack
BiTree PopBiTree(Stack* sta);//Element Out Stack
Status DestroyStack(Stack *sta);//Destroy List Stack
Status ClearStack(Stack* sta);//Clear Stack
Status StackEmpty(Stack sta);//Judge Stack Whether Empty
int StackLength(Stack sta);//Get the length of Stack
BiTree GetTop(Stack sta);//Get the top Element of Stack

//Status Push(Stack *sta,int data);//????
// Pop(Stack *sta);//????

Status StackTraverse(Stack sta,Status (*visit)(BiTree));//Traverse Stack
Status TraverseBaseToTop(Ele* Ptmp,Status (*visit)(BiTree));//??????

//////////////////////////////////////////////////TAG STACK/////////////////////////////////////////////////////////////

typedef struct TAGEle{
    int data;
    struct TAGEle* pre;
}TAGEle;

typedef struct TAGStack{
    TAGEle* top;
    TAGEle * base;
    int Stacksize;
}TAGStack;

Status TAGStackInit(TAGStack* st);//链栈初始化
Status TAGStackIn(TAGStack* sta,int  data);//元素入栈
int TAGStackOut(TAGStack* sta);//元素出栈
Status TAGStackEmpty(TAGStack sta);//判断栈是否为空
int TAGGetTop(TAGStack sta);//获取栈顶元素
Status TAGSetTopData(TAGStack* s,int Ndata);//设置栈顶元素值

///////////////////////////////////////////////其他//////////////////////////////////////////////////////////////////////

char CreateData(TElemType data);//用于创建数据赋值给树节点的值域
int NumOfNode(BiTree T);//返回此二叉树中结点的个数

#endif //BITREE_LINK_BITREE_H
